package demo.hw;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class _跳马2 {
    public static void main(String[] args) {
        /**
         * 3x5
         * · · · · ·
         * · · 0 · ·
         * · · * · ·
         * 计算从(1,2)到(3,2)最短步数
         *
         * 1 2 3 2 1
         * 4 3 0 3 4
         * 1 2 3 2 1
         */
        int m = 3;
        int n = 5;
        int[] start = {1, 2};
        int[] tar = {2, 2};

        int[][] dist = new int[m][n];

        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], -1);
        }
        bfs(start, dist, m, n);
        System.out.println(dist[tar[0]][tar[1]]);
    }

    // bfs计算到起始位置到每个点位最小距离
    private static void bfs(int[] horse, int[][] dist, int m, int n) {
        int[][] dirs = {
                {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}
        };

        int x = horse[0], y = horse[1];
        Queue<int[]> queue = new LinkedList<>();
        dist[x][y] = 0;
        queue.offer(new int[]{x, y});

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int dx = curr[0];
            int dy = curr[1];
            int step = dist[dx][dy];

            for (int[] dir : dirs) {
                int nx = dx + dir[0];
                int ny = dy + dir[1];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] == -1) {
                    dist[nx][ny] = step + 1;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
    }
}
